#include <stdio.h>
#include "graph.h"

#define SUCCESS 0
#define ERROR -1

Graph* create_graph()
{
    Graph *graph;
    graph = (Graph *)malloc(sizeof(Graph)); 
    graph->vertex_head= NULL;
    graph->num_vertices = 0;

    return graph;
}

int insert_vertex(Graph *graph, Vertex *vertex)
{
    Vertex *v = graph->vertex_head; 
    while(v && v->next)
    {
        if(v->vertex_id == vertex->vertex_id)
        {
            printf("Vertex %d is already in the graph\n", vertex->vertex_id);
            return ERROR;
        }
        v = v->next;   
    }

    // Link the new vertex to the vertex list
    if(v!=NULL)
    { 
        v->next = vertex;
    }
    else
    {
        graph->vertex_head = &(*vertex);
    }

    graph->num_vertices++;
    return SUCCESS;
}

Vertex* get_last_vertex(Graph* graph)
{
    Vertex *v = graph->vertex_head;
    while(v && v->next)
    {
        v = v->next;
    }
    return v;
}

/* \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ */

int insert_edge
(
    Graph *graph, 
    Vertex *vertex1, 
    Vertex *vertex2, 
    double weight
)
{
    // Check if vertex1 is in the graph
    Vertex *v = graph->vertex_head;
    while(v)
    {
        if(v->vertex_id == vertex1->vertex_id)
            break;
        v = v->next;
    }
    if(v == NULL)
    {
        printf("Vertex %d is not in the graph\n", vertex1->vertex_id);
        return -1;
    }
    vertex1->out_degree++;

    // Check if vertex2 is in the graph 
    Vertex *v2 = graph->vertex_head;
    while(v2)
    {
        if(v2->vertex_id == vertex2->vertex_id)
            break;
        v2 = v2->next;
    }
    if(v2 == NULL)
    {
        // Insert vertex2 to the graph
        insert_vertex(graph, vertex2);
        v2 = vertex2; 
    }

    Edge *e,*e1;

    // Create a new edge
    e1 = (Edge *)malloc(sizeof(Edge));
    e1->dest_vertex = vertex2;
    e1->weight = weight;
    e1->edge_ptr = NULL;
    e1->on_crit_path = 0;

    // Get the first edge of the vertex
    e = vertex1->edge_ptr;

    // If the vertex has some edges, link the new edge to the last edge
    if(e)
    {
        // Get the last edge of the vertex 
        while(e && e->edge_ptr)
        {
            e = e->edge_ptr;
        }
        
        e->edge_ptr = e1;
    }
    // If the vertex does not have any edges
    else
    {
        vertex1->edge_ptr = &(*e1);
    }

    // Increase the indegree 
    vertex2->in_degree++;

    return 0; 
}

void print_graph(Graph *graph)
{
    Edge *e;
    Vertex *v = graph->vertex_head;
    int i = 0; 
    while(v)
    {
        //printf("%s(%s)", v->vertex_id, v->next->vertex_id);
        printf("(%d)", v->vertex_id);

        e = v->edge_ptr;
        while(e)
        {
            printf("->%d (%f)", e->dest_vertex->vertex_id, e->weight);
            e = e->edge_ptr;
        }
        printf(" indegree: %d", v->in_degree);
        printf("\n");
        v = v->next;
    }
}

int generate_graph
(
    Graph *graph, 
    const char* dotName, 
    const char* pdfName
)
{
    FILE *fp;
    char commandStr[512];
    int result;
    Vertex *v, *nv;
    Edge *e; 

    fp = fopen(dotName, "w");
    if(fp == NULL)
    {
        printf("Can not open %s file to save MPI task graph.\n", dotName);
        return -1;
    }

    fprintf(fp, "digraph MPI_TASK_GRAPH {\n");

    v = graph->vertex_head;
    while(v)
    {
        e = v->edge_ptr;
        while(e)
        {
            //if(v->on_crit_path && e->dest_vertex->on_crit_path)
            if(e->on_crit_path)
            {
                fprintf(fp, "\t\"%d:\" -> \"%d:\" [color=red fontcolor=red label=\"%fs\"];\n",
                        v->vertex_id,
                        e->dest_vertex->vertex_id,
                        e->weight);
            }
            else
            {
                fprintf(fp, "\t\"%d:\" -> \"%d:\" [label=\"%fs\"];\n",
                        v->vertex_id, 
                        e->dest_vertex->vertex_id,
                        e->weight);
            }
            e = e->edge_ptr;
        }
        v = v->next;
    }

	fprintf(fp, "}");
	fclose(fp);
    sprintf(commandStr, "dot -Tpdf %s -o %s", dotName, pdfName);
    result = system(commandStr); 
    sprintf(commandStr, "gv %s &", pdfName);
    result = system(commandStr);
    return result;
}

void free_graph(Graph *graph)
{
    Edge *e;
    Vertex *v = graph->vertex_head;
    while(v)
    {
        e = v->edge_ptr;
        while(e)
        {
            free(e); 
            e = e->edge_ptr;
        }
        if(!v)
        {
            printf("free %d\n", v->vertex_id);
            free(v);
        }
        v = v->next; 
    }
}

/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ */

int compute_critical_path
(
    Path* topo_path, 
    double *length
)
{
    Node *n = topo_path->head;
    while(n)
    {
        Vertex *vertex = n->vertex;
        Edge *edge = vertex->edge_ptr;
        while(edge)
        {
            double temp = vertex->crit_duration + edge->weight; 
            Vertex *nvertex = edge->dest_vertex;
            if(nvertex->crit_duration <= temp)
            {
                nvertex->crit_duration = temp;
                nvertex->prev_crit_vertex = vertex;
            }
            edge = edge->edge_ptr;
        }
        n = n->next;
    }

    // Find the max duration
    double maxVal = 0.0;
    n = topo_path->head; 
    Vertex *max_vertex = NULL;
    while(n)
    {
        if(maxVal <= n->vertex->crit_duration)
        {
            maxVal = n->vertex->crit_duration;
            max_vertex = n->vertex;
        }
        n = n->next;
    }
    *length = maxVal;

    if(max_vertex==NULL)
    {
        printf("Error in finding the critical path\n");
        return ERROR;
    }

    // traverse the precurssors to get the critical path
    max_vertex->on_crit_path = 1;
    Vertex *prev_v = max_vertex->prev_crit_vertex;
    while(prev_v)
    {
        prev_v->on_crit_path = 1;
        prev_v = prev_v->prev_crit_vertex;
    }

    // Traverse the graph again to mark the edges on critical path
    n = topo_path->head;
    double crit_weight; 
    Vertex * v;
    Edge * e; 
    Edge * crit_e;
    while(n)
    {
        v = n->vertex;
        e = v->edge_ptr;
        crit_e = e;
        crit_weight = -1.0;
        while(e)
        {
            if(v->on_crit_path && e->dest_vertex->on_crit_path)
            {
                if(e->weight > crit_weight)
                {
                    crit_weight = e->weight; 
                    // unmark previous critical edge
                    crit_e->on_crit_path = 0;
                    e->on_crit_path = 1;
                    crit_e = e;
                }
            }
            e = e->edge_ptr;
        }
        n = n->next;
    }

    return SUCCESS;
}

/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ */

void topological_sort(Graph *graph, Path *path)
{
    Vertex *v = graph->vertex_head;

    path->head = NULL;
    
    while(v)
    {
        if(v->in_degree == 0)
        {
            visit(v, path);
        }
        v = v->next;
    }
}

void visit(Vertex *vertex, Path *path)
{
    if(!vertex->visited)
    {
        vertex->visited = 1;
        Edge* e = vertex->edge_ptr;
        while(e)
        {
            Vertex * nextV = e->dest_vertex;
            visit(nextV, path);
            e = e->edge_ptr;
        }
        insert(path, vertex);
    }
}

/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ */

void insert(Path *path, Vertex *vertex)
{
    Node * vhead = path->head;
    Node * newNode = malloc(sizeof(Node));
    newNode->vertex = vertex;
    path->head = newNode;
    newNode->next = vhead;
}

void append(Path *path, Vertex* vertex)
{
    Node * newNode = malloc(sizeof(Node));
    newNode->vertex = vertex;
    if(path->head == NULL)
    {
        path->head = newNode;
    }
    else
    {
        path->head->next = newNode;
    }
}

void print_path(Path *path)
{
    Node *n = path->head;
    while(n)
    {
        printf("%d ", n->vertex->vertex_id);
        n = n->next;
    }
    printf("\n");
}

void free_path(Path *path)
{
    Node *n = path->head;
    while(n)
    {
        free(n);
    }
}

